Computers have long used data structures to store data used by computer programs. Data structures contain data entries, or records, each of which can be identified using a value known as a data key. A data key is an identifier of an entry in the data structure and may be one of the fields of the data structure. Alternatively, the data key can be derived by applying some fixed function, such as a hash function, to one or more of the fields.
As a particular example, in a database storing employee information, an employee number may serve as a data key. Other information about the employee can be stored in the data structure fields associated with that particular key. Such other information would be accessible via the data key, for example, by calling a function with the data key as an argument. The number of fields that are available for each key is dependent on how the data structure is defined.
Data structures can be accessed for a number of reasons, including, for example, storing data in the data structure and retrieving data from the data structure. In either case, the data structure is typically accessed using a sequential processing method. For example, in searching for an entry having a data key matching a search key, a computer typically begins by comparing the search key with the data key corresponding to the first entry in the data structure. If the keys do not match, the computer repeats the comparison with successive entries in the data structure until an entry is found whose corresponding key matches the search key or until the computer reaches the last entry in the data structure. If the computer reaches the last entry in the data structure without finding an entry whose key matches the search key, the computer may notify the user that no entry was located.
A sequential processing method will locate an entry having a corresponding key that matches the search key, if such an entry exists in the data structure. In many cases, however, the data structure is non-ordered with respect to the data key of interest, such that the entries are not consecutive. For example, the data structure may be ordered with respect to one field, but non-ordered with respect to one or more other fields. As a result, to search for a particular entry, the computer compares the search key to the essentially random key values for consecutive entries until the computer finds an exact match. This process can be time-consuming, particularly for data structures having many entries.